package com.yun;

/**
 * Created by lsy
 * on 2020/12/10 9:06.
 * 阅读拉布拉多的算法集，看了回溯算法的思想，自己手动实现以下。
 * 回溯算法大致框架
 * traveBack(){
 * 做选择
 * traveBack(下一个选择);
 * 退回当前的选择
 * }
 *
 * !!!!NICE，一遍写出来了。有自己的思想。
 */
public class TheEightQueue1210 {
    private static final int QUEUE_NUM = 10;
    private int NUM = 0;

    public static void main(String[] args) {
        TheEightQueue1210 queue = new TheEightQueue1210();
        queue.traveBack(new int[QUEUE_NUM], 0);
        System.out.println(queue.NUM);
    }

    /**
     * 回溯遍历
     *
     * @param rows 放置情况：每一行放在第几个位置
     * @param n    当前放第n行
     */
    public void traveBack(int[] rows, int n) {
        if (n == QUEUE_NUM) {
            NUM++;
            return;
        }
        for (int i = 0; i < QUEUE_NUM; i++) {
            if (!isValid(rows, n, i)) {
                continue;
            }
            rows[n] = i;

            traveBack(rows, n+1);

        }
    }

    // 当前放置第n行的第i个位置，是否可以放
    private boolean isValid(int[] rows, int n, int i) {
        for (int j = 0; j < n; j++) {
            if (i == rows[j]) {
                // 一列返回false
                return false;
            }
        }
        for (int j = 0; j < n; j++) {
            if (n - j == Math.abs(i - rows[j])) {
                return false;
            }
        }
        return true;
    }
}
